Tags: best and worst case
What is the best case time complexity of the following code?
def insertion_sort(arr):
"""Sort `arr` in ascending order."""
n = len(arr)
for i in range(1, n):
x = arr[i]
j = i - 1
# find where to place x
while j >= 0 and x < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = x
\(\Theta(n)\). The best case occurs when the array is already sorted. Notice that in this case, the while loop will never actually execute.
Tags: best and worst case
What is the worst case time complexity of the following code?
def insertion_sort(arr):
"""Sort `arr` in ascending order."""
n = len(arr)
for i in range(1, n):
x = arr[i]
j = i - 1
# find where to place x
while j >= 0 and x < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = x
\(\Theta(n^2)\). The worst case occurs when the array is sorted in reverse order. In this case, the while-loop executes on every iteration of the for-loop, and must move x from its current position all the way to the beginning of the array.
Tags: best and worst case
What is the best case time complexity of the following function?
def foo(arr):
"""arr is an array of size n"""
for x in arr:
for y in arr:
if sum([x,y]) == 5:
return sum(arr)
return False
\(\Theta(n)\). In the best case, we return sum(arr) on the very first iteration.
Tags: best and worst case
What is the worst case time complexity of the following function?
def foo(arr):
"""arr is an array of size n"""
for x in arr:
for y in arr:
if sum([x,y]) == 5:
return sum(arr)
return False
\(\Theta(n^2)\). In the worst case, we never find x + y == 5, and go through all \(\Theta(n^2)\) iterations just to return False at the end.
Tags: best and worst case
What is the best case time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
previous = None
n = len(arr)
for x in arr:
if x == previous:
for i in range(n**2):
print('Equal!')
return
previous = x
\(\Theta(n)\)
Tags: best and worst case
What is the best case time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
previous = None
n = len(arr)
for x in arr:
if x == previous:
for i in range(n**2):
print('Equal!')
return
previous = x
\(\Theta(n)\)
Tags: best and worst case
What is the worst case time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
previous = None
n = len(arr)
for x in arr:
if x == previous:
for i in range(n**2):
print('Equal!')
return
previous = x
\(\Theta(n^2)\)
Tags: best and worst case
The below code takes in an array of numbers and returns the index of the first maximum. What is this code's best case time complexity?
def index_of_maximum(arr):
"""`arr` is an array with n elements."""
for i, x in enumerate(arr):
if x == max(arr):
return i
\(\Theta(n)\)
Tags: best and worst case
The below code takes in an array of numbers and returns the index of the first maximum.
def foo(arr):
"""`arr` is an array with n elements."""
for i, x in enumerate(arr):
if x == max(arr):
return i
What is the worst case time complexity of the function?
\(\Theta(n^2)\)
Tags: best and worst case
The code below takes in an array of \(n\) numbers and checks whether there is a pair of numbers in the array which, when added together, equal the maximum element of the array.
What is the best case time complexity of this code as a function of \(n\)? State your answer using asymptotic notation.
def exists_pair_summing_to_max(arr):
n = len(arr)
maximum = max(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] + arr[j] == maximum:
return True
return False
\(\Theta(n)\)
Tags: best and worst case
The code below takes in two lists, each containing \(n\) integers, and determines if the any number in the second list appears at least \(n/2\) times in the first list.
def boo(first_list, second_list):
"""first_list and second_list are both of size n"""
n = len(first_list)
for x in second_list:
count = 0
for y in first_list:
if x == y:
count += 1
if count >= n // 2:
return True
return False
What is the best case time complexity of this code as a function of \(n\)? State your answer using asymptotic notation.
\(\Theta(n)\)
What is the worst case time complexity of this code as a function of \(n\)? State your answer using asymptotic notation.
\(\Theta(n^2)\)
The best case is when the first element of the second list appears at least \(n/2\) times in the first list. In this case, the code will return True after iterating \(n/2\) times through the inner loop, taking \(\Theta(n)\) time total.
In the worst case, there is no element in the second list that appears \(n/2\) times in the first. We make all \(n\) iterations of the outer loop, and during each of the outer iterations, make \(n\) iterations of the inner loop, for a total of \(\Theta(n^2)\) time.
Tags: best and worst case
The code below takes in two lists, each containing \(n\) integers.
def are_lists_equal(list1, list2):
if len(list1) != len(list2):
return False
for i in range(len(list1)):
if list1[i] != list2[j]:
return False
return True
def foo(list1, list2):
if are_lists_equal(list1, list2):
for i in list1:
print(i)
else:
for i in list1:
for j in list2:
for k in range(len(list1)):
print(i, j, k)
What is the best case time complexity of foo as a function of \(n\)? State your answer using asymptotic notation.
The best case is where the lists are equal. In this case the time complexity is \(\Theta(n)\). The worst case is when the lists are not equal in which case the time complexity is \(\Theta(n^3)\).
Tags: best and worst case, binary search
What is the worst case time complexity of binary search on an array of size \(n\) under the assumption that the target is guaranteed to appear in the array more than \(n/6\) times? You may assume that the input array is sorted.
\(\Theta(1)\). When there are at least n/6 instances of the target, binary search will not recurse more than twice. On the first recursive call, the array is halved in size. On the second, the array is down to \(n/4\). Note that all of the \(n/6\) instances of the target must be in this chunk of size \(n/4\), and so the middle number must be an instance of the target, and binary search will terminate.
Since binary search cannot recurse more than twice, and since it does constant work on each recursion, the total time taken is bounded by a constant, no matter how large the input array is.
If this seems odd, think about a simpler case: when the target appears \(n/2\) times. In other words, a full half of the array is the target. In this case, we'll make only one call (or maybe two, depending on the value of the middle element). And so there, too, the number of calls is bounded by a constant, and the total time is \(\Theta(1)\).
Tags: best and worst case, mergesort
True or False: the best case time complexity of mergesort is \(\Theta(n)\).
False.
Mergesort doesn't stop early: it always splits the array in half all the way down and merges everything back together, no matter what the input is (even if it is already sorted). Each of the \(\Theta(\log n)\) levels of recursion does \(\Theta(n)\) merging work, so the best case is \(\Theta(n \log n)\), the same as the worst case.
Tags: best and worst case
True or False: the best case time complexity of mergesort is \(\Theta(n)\).
False.
Mergesort doesn't stop early: it always splits the array in half all the way down and merges everything back together, no matter what the input is (even if it is already sorted). Each of the \(\Theta(\log n)\) levels of recursion does \(\Theta(n)\) merging work, so the best case is \(\Theta(n \log n)\), the same as the worst case.
Tags: best and worst case, mergesort
Suppose arr is a list-of-lists with \(n\) inner lists, each containing \(n\) numbers. What is the best case time complexity of the following function?
import math
def average_median(arr):
"""Compute the mean of the row medians."""
msum = 0
for i, row in enumerate(arr):
mergesort(row) # sort the row using the mergesort algorithm
msum += row[math.floor(i / 2)]
return msum / len(arr)
\(\Theta(n^2 \log n)\). Mergesort takes \(\Theta(k \log k)\) time on an array of size \(k\) in every case, including the best case. The loop sorts \(n\) rows of size \(n\), taking \(\Theta(n \log n)\) time for each, and the rest of the loop body takes constant time. So the best case is \(\Theta(n^2 \log n)\).
Tags: best and worst case, mergesort
Your friend has written a modified version of mergesort that they claim has an improved best-case time complexity:
def better_mergesort(arr):
if is_already_sorted(arr):
return
else:
mergesort(arr)
Here, is_already_sorted is a function that takes in an array and returns True if and only if the array is in sorted order. Assume that is_already_sorted is implemented efficiently (meaning, it has the best possible time complexity). What is the best case time complexity of better_mergesort?
\(\Theta(n)\). The best case is when arr is already sorted, so that only is_already_sorted runs. Checking whether an array is sorted requires looking at every element, and can be done in \(\Theta(n)\) time by comparing each pair of adjacent elements. So the best case time complexity is \(\Theta(n)\).
Tags: best and worst case, theoretical lower bounds
Consider the following problem: given two sorted lists, A and B, each containing \(n\) numbers, determine if the two lists share an element in common. That is, determine if there is a number \(x\) which appears in both lists.
What is a tight theoretical lower bound for this problem? Again, you may assume that the lists are both sorted. State your answer in asymptotic notation as a function of \(n\).
\(\Theta(n)\)
(2 points) Briefly (in 50 words or less) describe an algorithm for solving this problem and state its worst case time complexity. To earn full credit, you should give the optimal algorithm, but partial credit will be awarded for sub-optimal solutions. You may write pseudocode if you like, but an explanation in words is also sufficient. Make sure that you only state one algorithm!
Here's an approach that takes \(\Theta(n)\); it's similar to what we did in lecture for the movie problem.
Start with i = j = 0. If A[i] == A[j], return True, since you've found an element in common. If A[i] > A[j], increment j, otherwise increment i. Takes \(\Theta(n)\) time.
The brute force approach also earns credit: Loop over all pairs, checking if A[i] == B[j] for each pair. This takes \(\Theta(n^2)\) time.